/**
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]
*/

// 非递归，借助一个【局部】【栈】
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root)
    {
        //
        vector<int> res;

        // 需要一个【栈】结构
        stack<TreeNode*> stk;

        TreeNode* p = root;

        //【外层】【循环】控制【出栈】与【压栈】
        while(p || stk.size())
        {
            //【内层】【循环】，依次压栈【所有】【左】子节点，并记录对应的 value
            while(p)
            {
                stk.push(p); // 压栈
                res.push_back(p->val); //【区别】记录的是【当前根节点】
                p = p->left; // 指向【左】子节点
            }
            // 此时整个树中【最左边】所有节点，都已经访问完毕
            // p 指向 3

            // 读取、出栈当前【栈顶】保存的【最下方】的【左】子节点
            p = stk.top();
            stk.pop();

            // 将当前节点的【右孩子】作为【子树】的【根节点】继续遍历
            p = p->right;
        }

        return res;
    }
};
